Albert Abramovich Muchnik (2 January 1934 – 14 February 2019) was a

Russian Russian(s) refers to anything related to Russia, including: *Russians (, ''russkiye''), an ethnic group of the East Slavic peoples, primarily living in Russia and neighboring countries *Rossiyane (), Russian language term for all citizens and peo ...

mathematician A mathematician is someone who uses an extensive knowledge of mathematics in their work, typically to solve mathematical problems. Mathematicians are concerned with numbers, data, quantity, structure, space, models, and change. History On ...

who worked in the field of foundations and

mathematical logic Mathematical logic is the study of formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of formal ...

. He received his Ph.D. from

Moscow State Pedagogical Institute Moscow State Pedagogical University or Moscow State University of Education is an educational and scientific institution in Moscow, Russia, with eighteen faculties and seven branches operational in other Russian cities. The institution had underg ...

in 1959 under the advisorship of

Pyotr Novikov Pyotr Sergeyevich Novikov (russian: Пётр Серге́евич Но́виков; 15 August 1901, Moscow, Russian Empire – 9 January 1975, Moscow, Soviet Union) was a Soviet mathematician. Novikov is known for his work on combinatorial proble ...

. Muchnik's most significant contribution was on the subject of relative computability. He and Richard Friedberg independently introduced the priority method which gave an affirmative answer to

Post's problem In computer science and mathematical logic the Turing degree (named after Alan Turing) or degree of unsolvability of a set of natural numbers measures the level of algorithmic unsolvability of the set. Overview The concept of Turing degree is fund ...

regarding the existence of

recursively enumerable In computability theory, a set ''S'' of natural numbers is called computably enumerable (c.e.), recursively enumerable (r.e.), semidecidable, partially decidable, listable, provable or Turing-recognizable if: *There is an algorithm such that the ...

Turing degrees between 0 and 0' . This result, now known as the

Friedberg–Muchnik theorem In mathematical logic, the Friedberg–Muchnik theorem is a theorem about Turing reductions that was proven independently by Albert Muchnik and Richard Friedberg in the middle of the 1950s. It is a more general view of the Kleene–Post theorem. T ...

, opened study of the Turing degrees of the recursively enumerable sets which turned out to possess a very complicated and non-trivial structure. Muchnik also made significant contributions to Medvedev's theory of mass problems, introducing a generalisation of Turing degrees, called "Muchnik degrees", in 1963. Muchnik also elaborated

Kolmogorov Andrey Nikolaevich Kolmogorov ( rus, Андре́й Никола́евич Колмого́ров, p=ɐnˈdrʲej nʲɪkɐˈlajɪvʲɪtɕ kəlmɐˈɡorəf, a=Ru-Andrey Nikolaevich Kolmogorov.ogg, 25 April 1903 – 20 October 1987) was a Sovi ...

's proposal of viewing

intuitionism In the philosophy of mathematics, intuitionism, or neointuitionism (opposed to preintuitionism), is an approach where mathematics is considered to be purely the result of the constructive mental activity of humans rather than the discovery of f ...

as "calculus of problems" and proved that the lattice of Muchnik degrees is Brouwerian. Muchnik was married to the Russian mathematician Nadezhda Ermolaeva. Their son Andrej, who died in 2007, was also a mathematician working in foundations of mathematics.S. I. Adian, A. L. Semenov, V. A. Uspenskii
''Andrei Albertovich Muchnik''

Uspekhi Matematicheskikh Nauk ''Uspekhi Matematicheskikh Nauk'' (russian: Успехи математических наук) is a Russian mathematical journal, published by the Russian Academy of Sciences and Moscow Mathematical Society and translated into English as ''Russi ...

, vol. 62 (2007), no. 4, pp. 140–144 He died in February 2019.

Selected publications

*A. A. Muchnik, ''On the unsolvability of the problem of reducibility in the theory of algorithms''.

Doklady Akademii Nauk SSSR The ''Proceedings of the USSR Academy of Sciences'' (russian: Доклады Академии Наук СССР, ''Doklady Akademii Nauk SSSR'' (''DAN SSSR''), french: Comptes Rendus de l'Académie des Sciences de l'URSS) was a Soviet journal that ...

(N.S.), vol. 108 (1956), pp. 194–197

References

External links

Albert Mucknik's personal webpage

Keldysh Institute of Applied Mathematics The Keldysh Institute of Applied Mathematics (russian: Институт прикладной математики им. М.В.Келдыша) is a research institute specializing in computational mathematics. It was established to solve computati ...

1934 births 2019 deaths Mathematical logicians Russian mathematicians Moscow State Pedagogical University alumni {{russia-mathematician-stub